package org.ala.everyday;

import java.util.TreeMap;

/**
 * 你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
 *
 * 运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。
 *
 * 请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。
 *
 *
 *
 * 示例 1：
 *
 * 输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
 * 输出：3
 * 解释：
 * 可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
 * 选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
 * 可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。
 * 示例 2：
 *
 * 输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
 * 输出：0
 * 解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。
 *
 *
 * 提示：
 *
 * chargeTimes.length == runningCosts.length == n
 * 1 <= n <= 5 * 104
 * 1 <= chargeTimes[i], runningCosts[i] <= 105
 * 1 <= budget <= 1015
 *
 * @author ala
 * @data 2024-09-13 07:57
 */
public class Q2398 {

    public static void main(String[] args) {
        Q2398 q = new Q2398();

//        int[] chargeTimes = {3,6,1,3,4},
//              runningCosts = {2,1,3,4,5};
//        int budget = 25;

//        int[] chargeTimes = {11,12,19},
//              runningCosts = {10,8,7};
//        int budget = 19;

        int[] chargeTimes = {19,63,21,8,5,46,56,45,54,30,92,63,31,71,87,94,67,8,19,89,79,25},
              runningCosts = {91,92,39,89,62,81,33,99,28,99,86,19,5,6,19,94,65,86,17,10,8,42};
        int budget = 85;

        System.out.println(q.maximumRobots(chargeTimes, runningCosts, budget));
    }

    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        N = chargeTimes.length;
        return V2(chargeTimes, runningCosts, budget);
    }
    protected int N;


    /**
     *  1）TreeMap维护窗口内最大的chargeTimes，前缀和维护runningCosts的区域和
     *  2）滑窗，r - l + 1即为k
     *      若窗口内的值 > budget：窗口左移，同时出窗口的l，累减他的ct出现次数。若减成0，remove掉
     *      若窗口内的值 <= budget：继续右移
     */
    protected int V1(int[] cts, int[] rcs, long b) {
        //  求rcs的前缀和
        long[] ps = new long[N + 1];
        for (int i = 1 ; i <= N ; i++) {
            ps[i] = ps[i - 1] + rcs[i - 1];
        }

        //  记录窗口内的ct
        TreeMap<Integer, Integer> ctm = new TreeMap<>();
        //  滑窗
        int res = 0;
        for (int l = 0, r = 0 ; r < N ; r++) {
            //  累加rc[i]的出现次数
            ctm.merge(cts[r], 1, Integer::sum);

            //  如果窗口内的值超过budget，缩小窗口
            while (l <= r && (long)ctm.lastKey() + (r - l + 1) * (ps[r + 1] - ps[l]) > b) {
                if (ctm.merge(cts[l], -1, Integer::sum) == 0) {
                    ctm.remove(cts[l]);
                }
                l++;
            }

            res = Math.max(res, r - l + 1);
        }
        return res;
    }

    /**
     * 单调队列优化TreeMap
     */
    protected int V2(int[] cts, int[] rcs, long b) {
        //  前缀和
        long[] ps = new long[N + 1];
        for (int i = 1 ; i <= N ; i++) { ps[i] = ps[i - 1] + rcs[i - 1]; }

        //  单调队列维护窗口内最大的cts
        int[] queue = new int[N];
        int ql = 0, qr = -1, qs = 0;
        //  滑窗
        int res = 0;
        for (int l = 0, r = 0 ; r < N ; r++) {
            //  如果cts[r]大于队列右端，右端出队
            while (qs > 0 && cts[r] > queue[qr]) {
                qr--;
                qs--;
            }
            queue[++qr] = cts[r];
            qs++;
            //  检测窗口内值是否超过b
            while (l <= r && queue[ql] + (r - l + 1) * (ps[r + 1] - ps[l]) > b) {
                if (cts[l] == queue[ql]) {
                    ql++;
                    qs--;
                }
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }

}
